/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <iostream>

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
	treeHeight = -1; //when constructing a tree default height is 1
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
RC rc_mes;
rc_mes = pf.open(indexname, mode);
    return rc_mes;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	rootPid = -1;
	treeHeight = 0;
    return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 
 
	
insertintoparent()
{
if(no parent)
{
create new nonleaf node as root
insert midkey into it
increas height of tree;
}
else
{
find parent node 
if (insert midkey to parent is succesfful)
	write parent node
else 
{
	splitparentnode and insert midkey;
		insertintoParent();
}
}
}
 */
 
 void insertIntoParent(int curHt, int midKey, PageId child_pid)
 {
	if(curHt == -1)
	{
		BTNonLeafNode root;
		root.initializeRoot(curr_root, midKey, child_pid);
		treeHeight++;
	}
	else
	{
		BTNonLeafNode parent;
		RC rc;
		locateParentNode(midKey, parent, curHt)
		try
		{
			rc = parent.insert(midKey, child_pid);
			if(rc != 0)
				throw rc;
			else
				parent.write(child_pid, pf);
		}
		catch (int mes)
		{
			BTNonLeafNode sibling;
			int newKey;
			rc = parent.insertAndSplit(midKey, child_pid, sibling, newKey);
			insertIntoParent(curHt - 1, newKey, child_pid);
		}
	
	}
 }
 
 /*
 find pageid for leafnode to key,rid
 read leafnode by pageid
 if(leafnode key , rid == 0) 
	write leafnode by pageid
else 
	leafnode insertandsplit
	write sibling node
	insertintoparent() recursively insert key of the new node to the parent leaf */
 
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	BTLeafNode leaf;
	IndexCursor cursor;
	locate(key, cursor);
	leaf.read(cursor.pid, pf)
	RC rc;
	try
	{
		rc = leaf.insert(key, rid);
		if(rc != 0)
			throw rc;
	}
	catch (int mes)
	{
		BTLeafNode sibling;
		int newKey;
		leaf.insertAndSplit(key, rid, sibling, newKey);
		PageId sib_pid = leaf.getNextNodePtr();
		sibling.write(sib_pid, pf);
		insertIntoParent(treeHeight, newKey, sib_pid);
	}
	
	
	return 0;
	/*
	int ht = treeHeight; 
	BTLeafNode leaf;
	leaf.read(rid.pid, pf);
	try
	{
		RC rc_mes = leaf.insert(key, rid);
		if(rc_mes != 0)
		{
			throw rc_mes;
		}
		else
			leaf.write(rid.pid, pf);
			
		return 0;
	}
	catch (int error)	//node is full need to split leaf
	{
		try
		{	
			ht++;
			BTLeafNode leaf2;
			int leaf2_key;
			BTNonLeafNode non_leaf;
			non_leaf.read(rid.pid, pf);
			RC rc_mes = leaf.insertAndSplit(key, rid, leaf2, leaf2_key);
			if(rc_mes != 0)
			{
				throw -1;
			}
			else
			{
				try	//add sibling node that we created to the split non_leaf
				{
					RC nl_rc;
					nl_rc = non_leaf.insert(leaf2_key, rid.pid);
					if(nl_rc != 0)
					{
						throw nl_rc;
					}
					else
					{
						non_leaf.write(leaf2.getNextNodePtr(), pf);
						return 0;
					}
				}
				catch (int nl_error) //if non_leaf is full need to split and repeat process for non_leaf
				{
					BTNonLeafNode non_leaf2;
					int non_leaf2_key;
					RC nl2_rc = non_leaf.insertAndSplit(leaf2_key, rid.pid, non_leaf2, non_leaf2_key);
					if(nl2_rc != 0)
					{
						return nl2_rc;
					}
					else
					{
						BTNonLeafNode parent;
						int par_pid = non_leaf2.locateChildPtr(non_leaf2_key, par_pid);
						parent.read(par_pid, pf);
						RC par_rc = parent.insert(non_leaf2_key, par_pid);
						parent.write(par_pid, pf);
					}
				}
			}
		}
		catch (int error2)
		{
			cout << "Split failed." << endl;
		}
	}
    return 0;*/
}

RC BTreeIndex::locateParentNode(int searchKey, BTNonLeafNode& parent, int parent_height)
{
	int curr_ht = 0;
	PageId child_pid;
	BTNonLeafNode root;
	root.read(rootPid,pf);
	root.locateChildPtr(searchKey, child_pid);
	bool at_ht = false;
	while(at_ht == false)
	{
		curr_ht++;
		if(curr_ht != parent_height)
		{
			nonleaf.read(child_pid,pf);
			nonleaf.locateChildPtr(searchKey,child_pid);
		}
		else
		{
			at_ht = true;
			parent.read(child_pid, pf);			
		}
	}
    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	/*
	if(treeHeight == 1)
	{
		BTLeafNode leaf;
		int eid;
		int key;
		RecordId rid;
		leaf.read(rootPid, pf);
		leaf.locate(searchKey, eid);
		leaf.readEntry(eid, key, rid);
		cursor.pid = rootPid;
		cursor.eid = rid.sid;
	}*/
	int curr_ht = 0;
	BTNonLeafNode root;
	PageId child_pid;
	root.read(rootPid,pf);
	root.locateChildPtr(searchKey, child_pid);
	bool at_leaf = false;
	while(at_leaf == false)
	{
		curr_ht++;
		if(curr_ht != treeHeight)
		{
			nonleaf.read(child_pid,pf);
			nonleaf.locateChildPtr(searchKey,child_pid);
		}
		else
		{
			at_leaf = true;
			BTLeafNode leaf;
			int eid,key;
			RecordId rid;
			leaf.read(child_pid, pf);
			leaf.locate(searchKey, eid);
			leaf.readEntry(eid, key, rid);
			cursor.pid = child_pid;
			cursor.eid = rid.sid;
		}
	}
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode leaf;
	leaf.read(cursor.pid, pf);
	leaf.readEntry(cursor.eid, key, rid);
	
	if(leaf.readEntry(cursor.eid+1, key, rid) != 0) //if next eid doesn't exist
	{
		cursor.eid = 0;
		cursor.pid = leaf.getNextNodePtr();
	}
	else
	{
		cursor.eid = cursor.eid + 1;
	}
	
    return 0;
}
